//https://leetcode.cn/problems/maximum-length-of-pair-chain/submissions/579489355/
class Solution {
public:

    int findLongestChain(vector<vector<int>>& pairs) {
        int n = pairs.size();
        sort(pairs.begin(), pairs.end(), [](vector<int>& p1, vector<int>& p2)
            {
                return p1[1] < p2[1];
            });
        // vector<int> dp(n,1);
        // int ret=1;
        // for(int i=1;i<n;++i)
        // {
        //     for(int j=i-1;j>=0;--j)
        //     {
        //         if(pairs[i][0]>pairs[j][1])
        //         {
        //             dp[i]=max(dp[i],dp[j]+1);
        //         }
        //     }
        //     if(ret<dp[i])
        //     ret=dp[i];
        // }
        // return ret;
        int ret = 1;
        int last = pairs[0][1];
        for (int i = 1; i < n; ++i)
        {
            if (pairs[i][0] > last)
            {
                ret++;
                last = pairs[i][1];
            }
        }
        return ret;
    }
};